Countable Wise Men with Hats
Warning: this essay contains solutions to math problems.
Here is a famous hat puzzle:
A king decides to give 100 of his wise men a test. If together they pass, they can go free. Otherwise, the king will execute all of them. The test goes as follows: the wise men stand in a line one after another, all facing in the same direction. The king puts either a black or a white hat on each wise man. The wise men can only see the colors of the hats in front of them. In any order they want, each one guesses the color of the hat on his own head. Other than that, the wise men cannot speak. To pass, no more than one of them may guess incorrectly. Given that they have time to agree on a strategy beforehand, how can they assure that they will survive?
Instead of discussing the puzzle above, I’d like to look at a different version. It is an infinite variation of the puzzle that my son Sergei brought back from the Canada/USA Mathcamp last year.
The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?
Oh, I forgot to mention: you are allowed to use the axiom of choice.
Here is the solution. You can build an equivalence relation on the possible placements of hats. To be equivalent, two ways of placing the hats should have the same tail. In other words, there is a person such that both hat arrangements to his right are the same. By the axiom of choice you can pick a representative in any equivalence class. The first wise man looks at all the other hats and calculates in how many places the tail differs from the representative of the class they picked. This is a finite number, and by stating one color or the other, he signals the parity of that number. After that, all the wise men say their colors from left to right. Everyone sees the tail and everyone hears the color choices of the people behind. So every wise man can reconstruct the color of his hat with this information. Only the first person may potentially be mistaken.
Many things about this solution bother me. Where is this country that can fit an infinite number of people? What kind of humans can see into infinity? How much time will this procedure take?
Aside from the practical matters, there are mathematical matters that bother me, too. By the axiom of choice you can pick an element in every class. The problem is that all of the wise men have to pick the same element. The axiom of choice claims the existence of a choice function, which picks an element in each set. So the function exists, but can we distribute this function to many wise men? Remember, they need to agree on this function the night before.
We already implicitly assumed that our wise men have a lot of magical abilities. So we can add to those the ability to go through all the possible tails and memorize the representatives for all the tails in one evening.
But still, I am very curious to know what follows from the axiom of choice. Tell me what you think: does the axiom of choice imply that we can distribute the choice function, or do we need a new axiom? In your opinion, will these wise men live?
Share:
Brenda:
wiseman(n) taps the left shoulder of wiseman(n+1) if that esteemed counselor is wearing a white hat, the right shoulder otherwise.
wiseman(0) says a random color to get things started.
alternately, there is a certain position at the tail of the line where everyone from that position forward is wearing the same color hat, even if it is just one person. Let’s call the position of the first person in that chain, n. Wiseman n-1 must be wearing the opposite color hat. Wiseman n-2 notices that and taps wiseman n-1 on the shoulder (if no touching is allowed, waits a certain amount of time). Wiseman n-1 then announces the color of his hat, as do everyone from Wiseman n to the last wiseman in the row.
Wiseman from n-1 to the end are no longer considered, and they keep working backward until Wiseman 1, having nobody behind him, takes a guess as to the color of his own hat.
6 August 2009, 9:33 ammisha:
They will not if they use the algorithm you suggested, because they will not have enough time to construct the choice function, which “exists” just because some crazy mathematicians want it to exist, and they postulate that it does. But such a choice function is a sheer fantasy, and using it is like deriving nonsense from nonsense. Another notorious example of such trickery is the Banach-Tarsky paradox. In his 1998 book “The Principles of Mathematics Revisited” Jaakko Hintikka suggests that the infinite choice is fine, if you can construct your choice function in a reasonable manner. It’s a nice read, and it gave me lots of laughs, one chapter is called “Axiomatic set theory: Frankenstein’s monster?” Quite a few people argue that while set theory is a nice language, it should not be taken too seriously, and is not a reasonable foundation for all the mathematics. For an example of alternatives, see some recent papers on arxiv.org by Nik Weaver. It looks like mathematics, thanks to more powerful computers, is moving away from pure mental acrobatics towards more practical matters of computation, I think it’s a good thing.
6 August 2009, 11:34 pmMaria Roginskaya:
The first person guess the coulor of his hat and than answer it after one minute of consideration if the person in front of him has white hat and in two minutes if he has a black one. Then the second person names the coulor of his hat (which he by that time knows) in one minute if the person in front of him has white hat and in two minutes if he has a black one, and so on. It is not in the spirit of the question as the time is an additional factor which is not named in the question, but if you want to be practical… 🙂
I like though the solution with the axiom of choice better: If you are dealing with infinity you have already left the mundane world and work with the abstraction. It is an old controversary in Mathematics if one should use the axiom of choise or not. As far to my knowledge there exists some mathematician who restrict themselves only to what can be proved without it. If one take on the Bourbaki’s position – the theory based on a subset of axioms have to be a subset of the theory based on the whole set. So, by excluding axiom of choice you get the theorems which are valid with axiom of choice (as far to my knowledge there is even some activity in keeping track which theorems require axiom of choice, and which are independent of it).
I, personally, find the axiom of choice very practical, as I consider my speciallity to be construction of counterexamples, and in that light the only impotant fact about the object constructed is that it exists.
What for the development of Mathematics – it is a matter of definitions: Where does it ends and Computer Sciences or Physics starts? There always be people who derive pleasure of the “mental acrobatics”, so I don’t think this part of Mathematics will die away (and I think it is a good thing).
7 August 2009, 3:12 amKonstantin Knop:
https://knop.livejournal.com/107564.html (russian text)
8 August 2009, 2:01 amTanya Khovanova:
The finite version of the hat puzzle appeared in the 23-rd All-Russian Mathematical Olympiad 1997. The author was Konstantin Knop.
9 August 2009, 9:35 amAkhil Mathew:
There’s also some discussion of a variant of this puzzle that doesn’t allow the other prisoners to hear the responses at https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/.
12 August 2009, 10:02 amTanya Khovanova:
Akhil,
Thank you very much for the link. My concerns with the infinite hats problem are very similar to the ones expressed by David Wilson’s comment there.
I also liked the blog itself (The Everything Seminar) and added it to my blogroll.
12 August 2009, 11:49 amDaran:
I partly agree with Misha. Unlike him (or her), I have no objection to the notion that a particular choice function exists, but the problem for our wise men is that there is no way of constructing one, consequently no way for them to obtain the information they need from it.
12 September 2009, 9:04 amAndrew:
Hi all!
I have been researching regarding the famous hat puzzle, and all the solutions I have found seem incorrect to me.
They all talk about counting hats of a certain color and responding depending on if that number is odd or even.
But NOWHERE in the puzzle it is written that the number of white and black hats is THE SAME! They may have 81 black and 19 white hats, for example. How do you solve that?
Cheers!
17 May 2010, 2:28 pmAndrew:
Oh, I think now I got it… Sorry. 🙁
17 May 2010, 2:33 pmChrist Schlacta:
the puzzle doesn’t state the order in which they must guess their own hat colour or the order in which they must say words, so once the second hat is placed, the first wiseman should say the colour of the hat in front of him directly. each wiseman simply remembers his own colour and states the colour of the person to the right. once the hats are placed, each wiseman indicates his colour as instructed, and only the first might be wrong unless their memory is fallible.
12 January 2011, 10:19 pmTanya Khovanova's Math Blog » Blog Archive » The Raven’s Hat:
[…] No. The answer is still the same, there is a strategy where not more than one sage is mistaken. See my blog post for the […]
21 January 2023, 12:20 pm